class Router {
public:
    int MemoryLimit;
    set<tuple<int, int, int>> Exist; //未转发的数据包 判重
    queue<tuple<int, int, int>> PacketQ; //packet队列
    map<int, pair<vector<int>, int>> Dest2Timestamps; //destination -> ([timestamp], Qhead)
    Router(int memoryLimit) { //最大数据包容量
        MemoryLimit=memoryLimit;
    }
    
    bool addPacket(int source, int destination, int timestamp) {
        auto packet=tuple(source, destination, timestamp);
        if(!Exist.insert(packet).second) return false;
        if(PacketQ.size()==MemoryLimit) forwardPacket();
        PacketQ.push(packet); //入队
        Dest2Timestamps[destination].first.push_back(timestamp);
        return true;
    }
    
    vector<int> forwardPacket() {
        if(PacketQ.empty()) return {};
        auto packet=PacketQ.front(); PacketQ.pop(); //出队
        Exist.erase(packet);
        auto [source, destination, timestamp]=packet;
        Dest2Timestamps[destination].second++; //指针后移
        return {source, destination, timestamp};
    }
    
    int getCount(int destination, int startTime, int endTime) {
        auto &[timestamps, head]=Dest2Timestamps[destination];
        auto left=ranges::lower_bound(timestamps.begin()+head, timestamps.end(), startTime);
        auto right=ranges::upper_bound(timestamps.begin()+head, timestamps.end(), endTime);
        return right-left;
    }
};

/**
 * Your Router object will be instantiated and called as such:
 * Router* obj = new Router(memoryLimit);
 * bool param_1 = obj->addPacket(source,destination,timestamp);
 * vector<int> param_2 = obj->forwardPacket();
 * int param_3 = obj->getCount(destination,startTime,endTime);
 */